package stack;

import java.util.Deque;
import java.util.LinkedList;

/*84. 柱状图中最大的矩形
        中心高度枚举的简化,单调栈
*
* */
public class LargestRectangleArea84 {
    public int largestRectangleArea(int[] heights) {
        if(heights.length==1){
            return heights[0];
        }
        int n=heights.length;
        int[] left=new int[n];
        int[]  right=new int[n];
        Deque<Integer> stack= new LinkedList<>();
        for(int i=0;i<n;i++){
            while(!stack.isEmpty() && heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            left[i]=stack.isEmpty()?-1:stack.peek();
            stack.push(heights[i]);
        }
        stack.clear();
        for(int i=n-1;i>=0;i--){
            while(!stack.isEmpty() && heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            right[i]=stack.isEmpty()?n:stack.peek();
            stack.push(heights[i]);
        }
        int res=0;
        int max=0;
        for (int i = 0; i < n; i++) {
            res=(right[i]-left[i]-1)*heights[i];
            max=Math.max(max,res);
        }
        return max;
    }
}
